package daily.year2024.m8;

public class d27 {
    class Solution1 {

        //解法一：递归
        int res, count, n;
        ListNode left;
        public int pairSum(ListNode head) {
            res = 0;
            count = 0;
            n = 0;
            left = head;
            dfs(head);
            return res;
        }
        private void dfs(ListNode right) {
            if(right == null) {
                return;
            }
            n++;
            dfs(right.next);
            if(count > n/2) {
                return;
            }
            int tmp = left.val + right.val;
            res = Math.max(tmp,res);
            left = left.next;
            count++;
        }
    }

    class Solution2 {
        //解法二：快慢指针+反转链表
        public int pairSum(ListNode head) {
            ListNode quick = head.next, slow = head;
            while(quick != null && quick.next != null) {
                slow = slow.next;
                quick = quick.next.next;
            }
            ListNode newList = reverseListNode(slow.next);
            slow.next = null;
            ListNode l1 = head, l2 = newList;
            int res = 0;
            while(l1 != null && l2 != null) {
                int tmp = l1.val + l2.val;
                res = Math.max(tmp,res);
                l1 = l1.next;
                l2 = l2.next;
            }
            return res;
        }

        private ListNode reverseListNode(ListNode head) {
            ListNode newHead = new ListNode();
            ListNode cur = head, next;
            while(cur != null) {
                next = cur.next;
                cur.next = newHead.next;
                newHead.next = cur;
                cur = next;
            }
            return newHead.next;
        }
    }
}
